描述

设计一个算法，找出只含素因子2，3，5 的第 n 小的数。 符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

我们可以认为1也是一个丑数

样例

如果n = 9， 返回 10

挑战

要求时间复杂度为O(n_log_n)或者O(n)

找了很久都没明白丑数几个意思,直到看到个公式: 2^i,3^j,5^k 10以内丑数为 n[2^i,3^j,5^k] 1 [0, 0, 0] 2 [1, 0, 0] 3 [0, 1, 0] 4 [2, 0, 0] 5 [0, 0, 1] 6 [1, 1, 0] 7 不存在 8 [3, 0, 0] 9 [0, 2, 0] 10 [1, 0, 1] 要返回的数是第n个,即输入9返回的并不是9(9是丑数但不是第九个),第9个是10 思路就是生成丑数数组,然后返回坐标为 n-1 的元素即可 Python3

class Solution: """ @param n: An integer @return: the nth prime number as description. """ def nthUglyNumber(self, n): L=[1] i2,i3,i5=0,0,0 for j in range(n): n2,n3,n5=L[i2]*2,L[i3]*3,L[i5]*5 m=min(n2,n3,n5) L+=[m] i2+=(m == n2) i3+=(m == n3) i5+=(m == n5) print(L) return L[n-1]

其中 i2+=(x) 当(x)为True时i2+=1 当(x)为False时i2+=0